/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2022-10-04
 * Time:16:41
 */

/**
 * 力扣921:使括号有效的最少添加
 */

public class minAddToMakeValid {
    public static void main(String[] args) {
        String s = "()))((";
        System.out.println(minAddToMakeValid(s));
    }
    public static int minAddToMakeValid(String s) {
        //返回 为使结果字符串 s 有效而必须添加的最少括号数。
        /**
         * 如果遇到左括号，则将左括号的个数加 1。
         * 如果遇到右括号，则需要和前面的左括号进行匹配，具体做法如下：
         *     如果左括号的个数大于 0，则前面有左括号可以匹配，因此将左括号的个数减 1，表示有一个左括号和当前右括号匹配；
         *     如果左括号的个数等于 0，则前面没有左括号可以匹配，需要添加一个左括号才能匹配，因此将添加次数加 1。
         * 遍历结束后，需要检查左括号的个数是否为 0。如果不为 0，则说明还有剩下的左括号没有匹配，对于每个剩下的左括号都需要添加一个右括号才能匹配，此时需要添加的右括号个数为剩下的左括号个数，将需要添加的右括号个数加到添加次数。
         */
        int len = s.length();
        int count = 0;
        int leftcount = 0;
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if (ch == '('){
                // 如果左括号的个数大于 0，则前面有左括号可以匹配，因此将左括号的个数减 1，表示有一个左括号和当前右括号匹配；
                leftcount++;
            }else{
                /**
                 * 如果左括号的个数等于 0，则前面没有左括号可以匹配，需要添加一个左括号才能匹配，因此将添加次数加 1。
                 * 遍历结束后，需要检查左括号的个数是否为 0。如果不为 0，则说明还有剩下的左括号没有匹配，
                 * 对于每个剩下的左括号都需要添加一个右括号才能匹配，此时需要添加
                 */
                if (leftcount > 0){
                    leftcount--;
                }else {

                    count++;
                }
            }
        }
        count += leftcount;
        return count;
    }
}
